package com.mdnote.practice.linked_list;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/20 
 * @description 876. 链表的中间结点
 */
public class LeetCode876 {

    public static void main(String[] args) {
        LeetCode876 leetCode876 = new LeetCode876();
        ListNode listNode = new ListNode(11);
        listNode.next = new ListNode(12);
        listNode.next.next = new ListNode(13);
        listNode.next.next.next = new ListNode(14);
        listNode.next.next.next.next = new ListNode(15);
        listNode.next.next.next.next.next = new ListNode(16);

        ListNode listNode1 = leetCode876.middleNode(listNode);
        System.out.println(listNode1.val);
    }

    public ListNode middleNode(ListNode head) {
        
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            if (fast.next.next == null) {
                // 偶数个元素
                return slow.next;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        
        return slow;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
